package com.cet.algorithm.二叉树.从中序与后序遍历序列构造二叉树;

import java.util.HashMap;
import java.util.Map;

/**
 * @program: algorithm
 * @description: 前序遍历和中序遍历序列构造二叉树
 * @author: 陈恩涛
 * @create: 2022-07-27 16:46
 **/
public class LC105 {

    public static void main(String[] args) {
        int[] preorder = {3, 9, 20, 15, 7};
        int[] inorder = {9, 3, 15, 20, 7};
        final TreeNode treeNode = new LC105().buildTree(preorder, inorder);
    }

    private Map<Integer, Integer> map = new HashMap<>(16);

    public TreeNode buildTree(int[] preorder, int[] inorder) {
        for (int i = 0; i < inorder.length; i++) {
            map.put(inorder[i],i);
        }
        return findNode(preorder, 0, preorder.length - 1, inorder, 0, inorder.length - 1);
    }

    private TreeNode findNode(int[] preorder, int preBegin, int preEnd, int[] inorder, int inBegin, int inEnd) {
        if (preBegin > preEnd || inBegin > inEnd) {
            return  null;
        }
        final Integer rootIndex = map.get(preorder[preBegin]);
        final TreeNode root = new TreeNode(inorder[rootIndex]);
        final int rightLen = inEnd - rootIndex;
        root.left = findNode(preorder, preBegin + 1, preEnd - rightLen, inorder, inBegin, rootIndex - 1);
        root.right = findNode(preorder, preEnd - rightLen + 1, preEnd, inorder, rootIndex + 1, inEnd);
        return root;
    }
}
